package tree;

import pojo.TreeNode;

/**
 * 功能描述: 平衡二叉树, 左子树高度和右子树高度差不超过1 ,
 *          1. 左子树 和 右子树的高度是一致的
 *          2. 左子树 比 右子树的高度大1
 *          3. 左子树 比 右子树的高度小1
 * 2024/05/18
 * <p>
 * ZhangYi
 */
public class BalanceTreeUtils {

    /**
     * 确认这个树要饭回的信息 1.平衡  2.获取 左树/右树 的高度
     */
    public static class Info{
        private boolean isBalance;
        private int height;

        public Info(boolean isBalance,
                    int height) {
            this.isBalance = isBalance;
            this.height = height;
        }
    }

    public static boolean isBalanceTree(TreeNode root){
        // 1. 边界值的处理
        if (root == null){
            return true;
        }
        return process(root).isBalance;
    }

    private static Info process(TreeNode root) {
        // 如果遇到了 叶子节点
        if (root == null){
            // 就是平衡的,同时高度为0
            return new Info(true, 0);
        }
        int height   = Math.max(process(root.left).height,process(root.right).height)+1;
        boolean isBalance = process(root.left).isBalance && process(root.right).isBalance
                && Math.abs(process(root.left).height - process(root.right).height) < 2;
        return new Info(isBalance, height);
    }

    public static void main(String[] args) {
        TreeNode root = generateBalanceTree();
        TreeNode root2 = generateNonBalanceTree();

        System.out.println(isBalanceTree(root));
        System.out.println(isBalanceTree(root2));
    }

    private static TreeNode generateNonBalanceTree() {
        TreeNode root = new TreeNode(1,
                                     "a");
        root.left = new TreeNode(2, "b");
        root.left.left = new TreeNode(4, "d");
        root.left.right = new TreeNode(5, "e");
        return root;
    }

    private static TreeNode generateBalanceTree() {
        TreeNode root = new TreeNode(1,
                                  "a");
        root.left = new TreeNode(2, "b");
        root.left.left = new TreeNode(4, "d");
        root.left.right = new TreeNode(5, "e");
        root.right = new TreeNode(3, "c");
        root.right.left = new TreeNode(6, "f");
        root.right.right = new TreeNode(7, "g");
        return root;
    }
}
